"""
idea1: counter 0 1 2 ， and use this counter return array, should loop twice, counter and change array
"""

array = [2, 0, 2, 1, 1, 0]


def solution1(nums):
    num0 = num1 = num2 = 0
    for num in nums:
        if num == 0:
            num0 += 1
        if num == 1:
            num1 += 1
        if num == 2:
            num2 += 1
    for i in range(num0):
        nums[i] = 0
    for i in range(num0, num0 + num1):
        nums[i] = 1
    for i in range(num0 + num1, len(nums)):
        nums[i] = 2

    return nums


print(solution1(array))

"""
idea2:

quick sort, one trip，less than in  one side , greater than in other side.

we can set 1 is base, 0 set to 1 left side, 2 set to 1 right side
"""


def solution2(nums):
    head = 0
    current = 0
    tail = len(nums) - 1
    while current <= tail:
        if nums[current] < 1:
            nums[current], nums[head] = nums[head], nums[current]
            head += 1
        elif nums[current] > 1:
            nums[current], nums[tail] = nums[tail], nums[current]
            tail -= 1
        current += 1
    return nums


print(solution2(array))